package sort.leetcode_56_medium_sort_greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class MergeIntervals {
    public static void main(String[] args) {
        int[][] temp = new int[][]{{1, 2}, {2, 3}};
        int[][] temp1 = merge(temp);
        for (int i = 0; i < temp.length; i++) {
            System.out.print(Arrays.toString(temp[i]));
        }
        System.out.println();
        for (int i = 0; i < temp1.length; i++) {
            System.out.println(Arrays.toString(temp1[i]));
        }

    }

    /**
     * 以下代码为合并两个区间的代码，通过合并两个区间 来转换出合并给定任意多的区间集合
     *
     * @param intervals 给定一二维数组，并假设二维数组中仅包含两个区间
     * @return 返回合并后的区间。
     */
    public static int[][] merge(int[][] intervals) {
        //最终返回的是合并后的区间，一个二维数组的形式，使用List集合，类型是int[]一个一维数组，那么整个List集合就是一个数组的数组（二维数组）
        List<int[]> res = new ArrayList<>();
        //无效数据
        if (intervals == null || intervals.length == 0) {
            //首先，res是一个集合，而返回值是一个数组类型，所以需要转换成数组类型，并且参数是一个二维数组。
            return res.toArray(new int[0][]);
        }
        //1. 对区间的开始端点进行排序，无法排序的类型要定义排序规则 1.创建comparator对象 2. Lambda表达式
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        //Lambda表达式写法
//        Arrays.sort(intervals, (a,b) -> a[0] - b[0]);

        /**
         * 2.首先可以去确定合并后的第一个区间的开始端点一定是intervals[0][0];
         *
         * 那么，什么样的区间需要合并？
         *
         * 假设给定数组(已排序)：{0,1},{2,3}，这两个区间没有重叠的部分所以不需要合并。
         * 假设给定数组(已排序)：{0,1},{1,9}, 此时两个区间在1这个节点处重叠，所以进行合并，合并后的区间为：{0,9}
         * 假设给定数组(已排序)：{1,4},{3,7}，这两个区间也有重叠部分，进行合并，合并后的区间：{1,7}
         *
         * 假设数组中就存在两个区间，那么可以分析出需要进行合并区间的情况：当第二个区间的开始端点 <= 第一个区间的结束端点;
         *
         * 进而可以推出，即使存在N个区间，那么需要进行合并仍然是上述这种情况。
         *
         */
        //假设就两个区间如何操作？
        //定义出第一个区间的开始端点和结束端点，结束端点与第二个区间的开始端点进行比较
        int start = intervals[0][0];
        int end = intervals[0][1];
        //第二个区间的开始端点 <= 第一个区间的结束端点，进行合并。
        if (intervals[1][0] <= end) {
            //如何合并？ 注意此时还可能存在的一种区间组合：{2,7},{3,4}，合并后的结果为：{2,7}，对于结束端点end来说，并没有改变
            //所以结束端点要选取两个区间中，较大的结束端点作为新的结束端点
            end = Math.max(end, intervals[1][1]);
        }
        res.add(new int[]{start, end});

        return res.toArray(new int[res.size()][]);
    }

    /**
     * 合并给定的区间集合，任意多少区间
     */
    public static int[][] mergeN(int[][] intervals) {
        //存储合并后的区间集合
        List<int[]> res = new ArrayList<>();
        //无效数据判断
        if (intervals == null || intervals.length == 0) {
            return res.toArray(new int[res.size()][]);
        }
        //对区间的 开始端点进行排序
//        Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] a1, int[] a2) {
                //升序规则
                return a1[0] - a2[0];
            }
        });

        /**
         * 对于任意区间，对区间进行遍历，然后进行前面的操作即可;
         */
        //数组索引从0开始
        int i = 0;
        while(i < intervals.length) {
            //开始端点
            int start = intervals[i][0];
            //结束端点
            int end = intervals[i][1];
            /**
             * 注意边界， 由于和下一个区间判断，所以 i 是不能到达下一个区间的。
             *
             * 这段代码只能合并一部分可以合并的区间
             *  比如给定区间集合：{1,2},{2,3}, {4,7}, {5,9}，那么下面代码合并{1,2},{2,3}后就会停止，无法继续。所以需要两重循环
             */
            while (i < intervals.length - 1 && intervals[i + 1][0] <= end) {
                end = Math.max(end, intervals[i + 1][1]);
                i++;
            }
            //跳出第二层循环时，说明有不重叠的区间，添加到List集合中
            res.add(new int[]{start,end});
            i++;
        }
        //返回结果：两种将List集合转换成数组的方式
        int[][] res1 = new int[res.size()][];
        for (int index = 0; index < res.size(); index++){
            res1[index] = res.get(index);
        }
        return res1;

//        return res.toArray(new int[res.size()][]);
    }

}
